package com.sort;

import java.util.Arrays;

/*
* 插入排序
*       时间复杂度：
* */
public class Insert_Sort {
    public static void main(String[] args) {
        int[] arr = {12,2,3,21,7};
        new Insert_Sort().InsertSort(arr);
    }

    public void InsertSort(int[] arr){
        int[] copy = Arrays.copyOf(arr, arr.length);
        for (int i = 1; i < copy.length; i++) {
            int temp = arr[i];

            int j = i;
            while (j > 0 &&temp < arr[j -1]){
                arr[j] = arr[j-1];
                j--;
            }

            if (j != i)
                arr[j] =temp;
        }
        System.out.println(Arrays.toString(arr));
    }
}
